package LeetCode;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class LC_632_SmallestRange {

    public static void main(String[] args) {

    }

    public class Solution {
        public int[] smallestRange(List<List<Integer>> nums) {
            int start = -1;
            int end = -1;
            int max = Integer.MIN_VALUE;
            int range = Integer.MAX_VALUE;
            PriorityQueue<Element> queue = new PriorityQueue<>(Comparator.comparingInt(e1 -> e1.val));
            for (int i = 0; i < nums.size(); i++) {
                Element e = new Element(nums.get(i).get(0), 0, i);
                queue.offer(e);
                max = Math.max(max, e.val);
            }
            while (queue.size() == nums.size()) {
                Element e = queue.poll();
                if (max - e.val < range) {
                    range = max - e.val;
                    start = e.val;
                    end = max;
                }
                if (e.index + 1 < nums.get(e.row).size()) {
                    e.index = e.index + 1;
                    e.val = nums.get(e.row).get(e.index);
                    queue.offer(e);
                    if (e.val > max) {
                        max = e.val;
                    }
                }
            }
            return new int[]{start, end};
        }

        class Element {
            int index;
            int row;
            int val;

            Element(int val, int index, int row) {
                this.val = val;
                this.index = index;
                this.row = row;
            }
        }
    }


}